Graphe moulin
| Graphe moulin | |
.svg&lang=fr) Graphe moulin Wd(5,4) | |
| Notation | Wd(k,n) |
|---|---|
| Nombre de sommets | (k − 1) n + 1 |
| Nombre d'arêtes | nk (k − 1) / 2 |
| Maille | 3 (pour k > 2) |
| Nombre chromatique | k |
| Indice chromatique | n (k − 1) |
modifier  |
|
En théorie des graphes, le graphe moulin Wd(k,n) est un graphe non orienté construit, pour deux entiers k ≥ 2 et n ≥ 2, en joignant n copies du graphe complet Kk à un sommet universel partagé. Autrement dit, il s'agit d'une somme, sur une clique à 1 seul sommet, de ces n graphes complets[1].
Propriétés
[modifier | modifier le code]Le graphe moulin Wd(k,n) a (k−1) n + 1 sommets et nk (k − 1) / 2 arêtes, il est de maille 3 (pour k > 2), de rayon 1 et de diamètre 2[2]. Il est 1-sommet-connexe parce que son sommet central est un point d'articulation ; cependant, comme les graphes complets à partir desquels il est formé, il est (k−1)-arête-connexe. Il est trivialement parfait et un graphe bloc.
Cas particuliers
[modifier | modifier le code]Par construction, le graphe moulin
- Wd(3,n) est le graphe d'amitié ou graphe de moulin hollandais (aussi noté Fn),
- Wd(2,n) est le graphe étoile (aussi noté Sn),
- Wd(3,2) est le graphe papillon.
Étiquetage et coloration
[modifier | modifier le code]Le graphe moulin a le nombre chromatique k et l'indice chromatique n (k−1). Son polynôme chromatique peut être déduit du polynôme chromatique du graphe complet et est égal à
Le graphe moulin Wd(k,n) n'est pas gracieux pour k > 5[3]. En 1979, Jean-Claude Bermond a conjecturé que Wd(4,n) est gracieux pour tout n ≥ 4[4]. Par une équivalence avec des familles parfaites de différences, elle a été vérifiée pour n ≤ 1000[5]. Bermond, Kotzig et Turgeon ont prouvé que Wd(k,n) n'est pas gracieux lorsque k = 4 et n = 2 ou n = 3, et lorsque k = 5 et m = 2[6]. Le graphe Wd(3,n) est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 1 (mod 4)[7].
Galerie
[modifier | modifier le code]
Références
[modifier | modifier le code]- Joseph A. Gallian, « A dynamic survey of graph labeling », Electronic Journal of Combinatorics, vol. DS6, , p. 1–58 (MR 1668059, lire en ligne).
- (en) Eric W. Weisstein, « Windmill Graph », sur MathWorld.
- K. M. Koh, D. G. Rogers, H. K. Teo et K. Y. Yap, « Graceful graphs: some further results and problems », Congressus Numerantium, vol. 29, , p. 559–571 (MR 0608456).
- J.-C. Bermond, « Graceful graphs, radio antennae and French windmills », dans Robin J. Wilson (éditeur), Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Pitman, coll. « Research notes in mathematics » (no 34), (ISBN 978-0273084358, OCLC 757210583, MR 0587620), p. 18–37.
- Gennian Ge, Ying Miao et Xianwei Sun, « Perfect difference families, perfect difference matrices, and related combinatorial structures », Journal of Combinatorial Designs, vol. 18, no 6, , p. 415–449 (DOI 10.1002/jcd.20259, MR 2743134).
- J.-C. Bermond, A. Kotzig et J. Turgeon, « On a combinatorial problem of antennas in radioastronomy », dans A. Hajnal et Vera T. Sos (éditeurs), Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, North-Holland, coll. « Colloquia mathematica Societatis János Bolyai » (no 18), (ISBN 978-0-444-85095-9, MR 0519261), p. 135–149.
- J.-C. Bermond, A. E. Brouwer et A. Germa, « Systèmes de triplets et différences associées », dans Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Éditions du Centre national de la recherche scientifique, coll. « Colloques internationaux du Centre National de la Recherche Scientifique » (no 260), (ISBN 978-2-222-02070-7, MR 0539936), p. 35–38.
